// 14.2.1　没重复元素的子集问题
// function subsets(nums) {
//     if (!Object(nums).length) { // 相当于 nums == null || !nums.length 
//       return [];
//     }
//     nums.sort((a, b) => a - b);
//     var result = [], candidate = [], end = nums.length;
//     function backtrack(start) {
//       result.push(candidate.concat());// 没有长度限制，直接放 result
//       for (var i = start; i < end; i++) {
//         candidate.push(nums[i]); // 试探
//         backtrack(i + 1); // 修改参数
//         candidate.pop(); // 不管成功与否，退回上一步
//       }
//     }
//     backtrack(0);
//     return result;
//   }
//   console.log(subsets([1, 2, 3]));
// 14.2.2　有重复元素的子集问题
// var subsetsWithDup = function (nums) {
//     if (!Object(nums).length) {
//       return [];
//     }
//     nums.sort((a, b) => a - b);
//     var result = [], candidate = [], end = nums.length, hash = {};
//     function backtrack(start) {
//       if (!hash[candidate]) { // 在结果中进行，防止重复
//         result.push(candidate.concat());// 没有长度限制
//         hash[candidate] = 1;
//       }
//       for (var i = start; i < end; i++) {
//         candidate.push(nums[i]); // 试探
//         backtrack(i + 1);
//         candidate.pop(); // 不管成功与否，退回上一步
//       }
//     }
//     backtrack(0);
//     return result;
//   }
//  console.log(subsetsWithDup([4, 4, 4, 1, 4]));
// 14.2.3　有重复元素的组合总和
// function combinationSum(nums, target) {
//     if (!Object(nums).length) {
//       return [];
//     }
//     nums.sort((a, b) => a - b);
//     var result = [], candidate = [], end = nums.length;
//     function backtrack(start, target) {
//       if (target === 0) { // 等于零，退出
//         result.push(candidate.concat());
//   return;
//       } 
//    if (target > 0) {// 等于零，进入
//         for (var i = start; i < end; i++) {
//           candidate.push(nums[i]); // 试探
//           // 注意这里i没有加1，因为我们可以重复使用该位置的元素
//           backtrack(i, target - nums[i]);
//           candidate.pop(); // 不管成功与否，退回上一步
//         }
//       }
//     }
//     backtrack(0, target);
//     return result;
//   };
// console.log(combinationSum([2, 3, 6, 7], 7));
// 14.2.4　无重复元素的组合总和
// function combinationSum(nums, target) {
//     if (!Object(nums).length) {
//       return [];
//     }
//     nums.sort((a, b) => a - b);
//     var result = [], candidate = [], end = nums.length, hash = {};
//     function backtrack(start, target) {
//       if (target === 0 && (!hash[candidate])) { // 等于零，退出
//           result.push(candidate.concat());
//           hash[candidate] = 1;
//         return;
//       } 
//   if (target > 0) {// 等于零，进入
//         for (var i = start; i < end; i++) {
//           candidate.push(nums[i]); // 试探
//           backtrack(i + 1, target - nums[i]); // i+1 !!!
//           candidate.pop(); // 不管成功与否，退回上一步
//         }
//       }
//     }
//     backtrack(0, target);
//     return result;
// }
// console.log(combinationSum([10,1,2,7,6,1,5], 8))

// 14.2.5　背包问题
// function knapsack01(n, weights, values, capacity) {
//     var allocation = new Array(n).fill(0); // 表示是否选中
//     var curValue = 0,
//       curWeight = 0,
//       maxValue = 0,
//       maxWeight = 0,
//       result = [];
//     function backtrack(start) {// start为物品的编号
//       if (start == n && curValue > maxValue) {
//          // 这只是其中一个候选项
//           maxValue = curValue;
//           maxWeight = curWeight;
//           result = allocation.concat();
//   return;
//       }
  
//        for (var i = 0; i < 2; i++) {
//          if (curWeight + i * weights[start] <= capacity) {
//            allocation[start] = i; // 0为不放进背包，1为放进背包
//            curWeight += i * weights[start];
//            curValue += i * values[start];
//            backtrack(start + 1);
//            curWeight -= i * weights[start];
//            curValue -= i * values[start];
//          }
//        }
//     }
//     backtrack(0);
//     console.log(maxValue, maxWeight, allocation);
//     return [maxValue, allocation];
//   }
//   knapsack01(5, [10, 20, 30, 40, 50], [20, 30, 65, 40, 60], 100);
// 14.2.6　装载问题
// function boatLoad(c1, c2, goods) {
//     if (!Object(goods).length) {
//       return false;
//     }
//     goods.sort();
//     var boats = [[], []];
//     var curr = [0, 0];
//     var max = [c1, c2];
//     function backtrack(start) {
//       if (start >= goods.length) {
//         return curr[0] <= max[0] && curr[1] <= max[1];
//       } else {
//         var cur = goods[start];
//         for (var i = 0; i < 2; i++) {
//           if (curr[i] + cur > max[i]) {
//             continue;
//           }
//           curr[i] += cur;
//           boats[i].push(cur);
//           if (backtrack(start + 1)) {
//             return true;
//           }
//           curr[i] -= cur;
//           boats[i].pop();
//         }
//       }
//       return false;
//     }
//     backtrack(0);
//     console.log(JSON.stringify(boats));
//     return boats;
//   }
  
//   boatLoad(50, 50, [30, 30, 10, 10]);
//   boatLoad(50, 50, [10, 40, 40]);
// 14.2.7　火柴棍拼摆正方形
// function makesquare(nums) {
//     if (Object(nums).length < 4) {
//       // 如果火柴数量不足4，肯定摆不出正方形
//       return false;
//     }
//     var sides = [[], [], [], []];
//     var total = nums.reduce(function(prev, el) {
//       return prev + el;
//     }, 0);
//     if (total % 4) {
//       // 如果不能被4整除
//       return false;
//     }
//     nums.sort((a, b)=> a - b).reverse();
//     var max = total / 4,
//       curr = [0, 0, 0, 0],
//       end = nums.length;
//     function backtrack(start) {
//       if (start >= end) {
//         return (
//           curr[0] == max &&
//           curr[1] == max &&
//           curr[2] == max &&
//           curr[3] == max
//         );
//       } else {
//         for (var i = 0; i < 4; i++) {
//           if (curr[i] + nums[start] > max) {
//             continue;
//           }
//           sides[i].push(nums[start]); // 这个可以不要
//           curr[i] += nums[start];
//           if (backtrack(start + 1)) {
//             return true;
//           }
//           sides[i].pop(); // 这个可以不要
//           curr[i] -= nums[start];
//         }
//       }
//       return false;
//     }
  
//     var result = backtrack(0);
//     console.log(JSON.stringify(sides), result);
//     return result;
//   }
  
//   makesquare([4, 3, 3, 2, 2, 1, 1]);
// 14.3.1　全排列问题
// function permute(nums) {
//     if (!Object(nums).length) {
//       return [];
//     }
//     var result = [],
//       candidate = [],
//       end = nums.length,
//       hash = {};
//       nums.sort();
//     function backtrack(start) {
//       if (start === end) {
//         result.push(candidate.concat());
//       } else {
//         for (var i = 0; i < end; i++) {
//           // 注意排列解，i需要从零开始，以确保它会加入某一个解
//           // hash是保证每一个解不同的关键
//           if (!hash[i]) {
//             hash[i] = 1;
//             candidate.push(nums[i]); // 试探
//             backtrack(start + 1);
//             candidate.pop(); // 不管成功与否，退回上一步
//             hash[i] = 0;
//           }
//         }
//       }
//     }
//     backtrack(0);
//     console.log(JSON.stringify(result));
//     return result;
//   }
//   permute([1, 2, 3]);
// 14.3.2　素数环
// var primes = {
//     2: 1,
//     3: 1
//   }
  
//   function isPrime(k) {
//     var i,
//         n = Math.sqrt(k);
//     if (primes[k]) {
//       return true;
//     }
//     if(k % 2 == 0){// 忽略偶数
//       return false;
//     }
//     for (i = 2; i <= n; i++) {
//       if (k % i == 0) {
//         return false;
//       }
//     }
//     return (primes[k] = true);
//   }
//   function getPrimeCircle(n) {
//     var array = [1], hash = {}, count = 0;
//     function backtrack(start) {
//       if (start == n) {
//         if (isPrime(array[0] + array[n - 1])) {
//           count++;
//         }
//       } else {
//         for (var i = 2; i <= n; i++) {
//           // 条件为没有使用过的值并且前一个数组值与下一个i+1的和为素数
//           if (!hash[i]) {
//             hash[i] = 1;
//             if (isPrime(array[start - 1] + i)) {
//               array[start] = i;
//               backtrack(start + 1);
//             }
//             hash[i] = 0;
//           }
//         }
//       }
//     }
//     backtrack(1);
//     console.log("count", n, count);
//     return count;
//   }
  
//   getPrimeCircle(3); // 0
//   getPrimeCircle(4); // 2
//   getPrimeCircle(8); // 4
//   getPrimeCircle(10); // 96
//   getPrimeCircle(12); // 1024
//   getPrimeCircle(14); // 2880
//   getPrimeCircle(16); // 81024
// 14.3.3　作业调度问题
// function schedule(n, timeA, timeB) {
//     var best = Infinity,
//       condidtate = [],
//       bestFlow = [],
//       hash = {};
//     function backtrack(start) {
//       if (start == n) {
//         var prevA = 0,
//           prevB = 0,
//           sum = 0;
//         for (var i = 0; i < n; i++) {
//           var index = condidtate[i];
//           var taskA = prevA + timeA[index];
//           var taskB = Math.max(taskA, prevB) + timeB[index];
//           prevA = taskA;
//           prevB = taskB;
//           sum += taskB;
//         }
//         if (sum < best) {
//           best = sum;
//           bestFlow = condidtate.concat();
//         }
//       } else {
//         for (var i = 0; i < n; i++) {
//           if (!hash[i]) {
//             condidtate.push(i);
//             hash[i] = 1;
//             backtrack(start + 1);
//             condidtate.pop();
//             hash[i] = 0;
//           }
//         }
//       }
//     }
//     backtrack(0);
//     console.log("最小完成时间和", best);
//     console.log("最佳调度顺序为", bestFlow);
//     return [best, bestFlow];
//   }
//   schedule(3, [2, 3, 2], [1, 1, 3]);
//   schedule(5, [2, 4, 3, 6, 1], [5, 2, 3, 1, 7]); // [4,0,2,1,3]
// 14.3.4　八皇后问题
// function findQueen() {
//     var result = [], path = [],
//       column = {}, mainDiagonal = {}, backDiagonal = {};
//     function isSafe(row, col) {
//       return (
//         !column[col] &&
//         !mainDiagonal[-(row - col)] &&
//         !backDiagonal[row + col]
//       );
//     }
//     function backtrack(row) {
//       if (row == 8) {
//         result.push(path.concat());
//       } else {
//         for (var col = 0; col < 8; col++) {
//           if (isSafe(row, col)) {
//             // 当前位置可放置
//             path[row] = col; // 标记放置的位置
//             column[col] = true; // 当前皇后所在列
//             mainDiagonal[-(row - col)] = true; // 皇后所在的对角线在第一行的列号
//             backDiagonal[row + col] = true; // 皇后所在的反对角线在第一行的列号
//             backtrack(row + 1); // 下一行上的皇后
//             column[col] = false;
//             mainDiagonal[-(row - col)] = false;
//             backDiagonal[row + col] = false;
//           }
//         }
//       }
//     }
//     backtrack(0); // 先放第一行的皇后
//     console.log("总共",result.length);
//     return result.length;
//   }
//   findQueen();